package pro.softzhang.algo.lc0;

import pro.softzhang.algo.common.ListNode;

/**
 *
 */
public class LC23_MergeKSortedLists {
    public static void main(String[] args) {

    }

    /**
     *
     */
    static
    class LC23_Solution {
        public ListNode mergeKLists(ListNode[] lists) {
            if (lists == null || lists.length == 0) {
                return null;
            }
            return doMergeKLists(lists, 0, lists.length);
        }

        private ListNode doMergeKLists(ListNode[] lists, int start, int end) {
            if(start + 1 == end) {
                return lists[start];
            }

            int middle = (start + end) / 2;
            return merge(doMergeKLists(lists, start, middle), doMergeKLists(lists, middle, end));
        }

        private ListNode merge(ListNode head1, ListNode head2) {
            ListNode dummy = new ListNode(0), current = dummy;
            while (head1 != null && head2 != null) {
                if(head1.val < head2.val) {
                    current.next = head1;
                    head1 = head1.next;
                } else {
                    current.next = head2;
                    head2 = head2.next;
                }
                current = current.next;
            }
            current.next = (head1 == null ? head2 : head1);
            return dummy.next;
        }
    }
}